package GuessNumberHigherorLowerII;

public class Solution {
    public int getMoneyAmount(int n) {
        int[][] f=new int[n+2][n+2];
        for (int i=1;i<=n;i++)
        	f[i][i]=0;
        for (int i=1;i<=n;i++)
        	for (int j=1;j<=n-i;j++){
        		f[j][i+j]=Integer.MAX_VALUE;
        		for (int k=j;k<=i+j;k++)
        		f[j][i+j]=Math.min(f[j][i+j], Math.max(f[j][k-1], f[k+1][i+j])+k);
        	}
        return f[1][n];
    }
    public static void main(String args[]){
    	Solution so=new Solution();
    	System.out.println(so.getMoneyAmount(2));
    }
    
}
